#include <algorithm>
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

class Solution {
    using ll = long long;

public:
    long long coutPairs(vector<int>& nums, int k)
    {
	unordered_map<int, int> gcdFreq;
	for (int num : nums) gcdFreq[__gcd(k, num)]++;

	vector<int> factors;
	for (auto [key, val] : gcdFreq) factors.push_back(key);
	sort(begin(factors), end(factors));
	if (factors[size(factors) - 1] == k) factors.pop_back();
	// for (int num : factors) printf("%6d", num);

	// for (int num : nums) printf("%6d", __gcd(k, num));
	int length = size(nums);

	ll res = (2LL * (length - 1) - gcdFreq[k] + 1) * gcdFreq[k] / 2;
	for (int i = factors[0] == 1 ? 1 : 0, len = size(factors); i < len; ++i) {
	    int cur_factor = factors[i], factor = k / cur_factor, Common_factor = max(cur_factor, factor);
	    // printf("(%6d,%6d)\n", cur_factor, Common_factor);
	    auto factor_itr = lower_bound(begin(factors), end(factors), Common_factor);
	    if (Common_factor == cur_factor) {
		if (1LL * Common_factor * Common_factor % k == 0) res += gcdFreq[Common_factor] * (gcdFreq[Common_factor] - 1) / 2;
		++factor_itr;
	    }
	    for (auto end_itr = end(factors); factor_itr != end_itr; ++factor_itr) {
		int match_factor = *factor_itr;
		if (__gcd(match_factor, factor) == factor) res += gcdFreq[cur_factor] * gcdFreq[match_factor];
	    }
	}
	return res;
    }
};

int main()
{
    [[maybe_unused]] Solution solution;
    return 0;
}
